package 力扣题库;

import java.util.ArrayList;
import java.util.List;

public class p235二叉搜索树的最近公共祖先 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //一次遍历
        //p、q结点一起遍历，就省去了存储路径需要的空间
        TreeNode ancestor=root;

        while (true) {
            if (ancestor.val<p.val && ancestor.val<q.val) {
                ancestor=ancestor.right;
            }else if (ancestor.val>p.val && ancestor.val>q.val) {
                ancestor=ancestor.left;
            }else {
                //p、q结点值，和当前根节点值比较，一大一小，则最近公共祖先就是 当前根节点
                break;
            }
        }
        return ancestor;
    }

    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        //两次遍历
        //分别在二叉搜索树中找 p、q结点，保存寻找的路径
        //比较两条路径，当路径中出现不一致时，则前一个则为最近公共祖先
        if (root.left==null && root.right==null) {
            return root;
        }

        List<TreeNode> pathP=getPath(root,p);
        List<TreeNode> pathQ=getPath(root,q);

        TreeNode ancestor=null;
        for (int i = 0; i <pathP.size() && i<pathQ.size(); i++) {
            if (pathP.get(i)==pathQ.get(i)) {
                ancestor=pathP.get(i);
            }else {
                //不相等时就结束，最近公共祖先为上一次遍历的结果
                break;
            }
        }
        return ancestor;
    }

    private List<TreeNode> getPath(TreeNode root, TreeNode target) {
        List<TreeNode> path=new ArrayList<>();

        TreeNode node=root;
        while (node!=target) {
            path.add(node);
            if (node.val > target.val) {
                //当前根节点值 大于 目标节点值，则在左子树找目标节点
                node=node.left;
            }else {
                //当前根节点值 小于 目标节点值，则在右子树找目标节点
                node=node.right;
            }
        }
        path.add(node);//最后把target结点放入路径中
        return path;
    }
}
 